1. Field of the Invention
The method and apparatus of the present invention relates to the field of digital halftoning. More particularly, the present invention relates to the storage of halftone cells in an optimum manner to save memory space while maintaining performance.
2. Art Background
The technique of halftoning is widely used in the printing industry for printing continuous tones of images, such as photographs, in a discrete form using a limited number of colors. For example, a monochrome image, such as photographs which appear in newspapers, are represented using two colors, black and white, and are produced typically by generating black dots on white paper. Color images, such as those found in magazines or newspapers, are represented by a small limited number of colors. Halftoning takes advantage of spatial integration in order to generate the image. Spatial integration is performed by the eye when viewing a small area from a large viewing distance wherein the eye averages fine detail within the small area and records only the overall intensity and color of the area.
By grouping multiple display elements into small grids or matrices, called halftone grids, the spatial resolution of the display output is decreased and the overall intensity levels or gray levels representable in an area is increased. For example, by grouping four display elements into a 2.times.2 matrix, the spatial resolution of the display output is decreased by half, but the amount of gray levels representable are increased to five.
The halftone grid is defined by mapping a uniform grid of small matrices, referred to as halftone cells, over the display device output pixel array (hereinafter referred to as the display space). The halftone grid has a frequency (the number of halftone cells per unit measure in the display space) and an angle (the orientation of the grid relative to the display space coordinate system). Each display element (referred to as a "pixel") of the display space corresponds to one element in the halftone cell. An area of the display screen can be made to approximate a shade of gray by turning a certain amount of the pixels within the area on (e.g. "white") or off (e.g. "black") in a predetermined pattern and sequence. In a display device such as a printer, the background is initialized to be white reflecting the fact that the image will be subsequently output to be printed on white paper and the pixels actuated are output as black "dots" reflecting the ink printed on the white paper. In a display device such as a computer graphic display device, the background is typically initialized to a black or dark color and the pixels actuated are "turned on" and appear as a white dot or light color on the screen. For purposes of explanation, the following description will refer to actuated pixels as being white. However, it is obvious to one skilled in the art that depending upon the system and output device, the actuated pixels may be other predetermined colors. In particular, in a corresponding printed image, the actuated pixels would be black.
Numerically, the gray level represented within a cell is the ratio of the number of pixels that are white to the total number of pixels in that cell. As a cell's gray value varies from black to white, increasingly more pixels in each cell change from black to white in a defined sequence. The order in which pixels change from black to white for increasing gray levels is specified by a user with a mathematical function called a dot or spot function. The spot function is used to calculate a plurality of threshold values, one value associated with each display element in the halftone cell. The differing magnitudes of the threshold values dictate the sequence in which pixels change from black to white for increasing gray level, that is, the threshold values are compared to the value representative of the desired intensity level. If the threshold value associated with a particular display pixel is greater than the desired intensity level of an area, the pixel is actuated. For further information on the halftoning process, see, Foley, et al., Computer Graphics, Principles and Practice, Second Edition, pp 569-573 (Addison-Wesley Publishing 1990); Ulichney, Digital Halftoning, (MIT Press 1987); Adobe Systems, Inc., POSTSCRIPT Language Reference Manual, pp 84-87 (Addison-Wesley Publishing 1986).
Typically, one binary representation of the halftone cell for each different intensity level is calculated according to the user specified spot function, halftone frequency and halftone angle. This binary representation is called a gray pattern. A collection of gray patterns for all possible intensity levels are precomputed and stored in memory. When generating a halftone image, the gray pattern for a particular intensity is then retrieved from memory as needed to determine the pixels to be actuated. The more pixels which compose a halftone cell, the greater the number of different intensities that can be represented and the greater the amount of memory required to store the gray patterns.
The threshold values generated by the spot function are dependent upon the location of the pixels in the halftone cell relative to the center of the halftone cell. If each halftone cell is consistently aligned with the pixels in the display space, a small halftone cell can be used to replicate across the entire display space and a single threshold array can be employed to determine the order of the pixels to be actuated to render an entire image. However, typically the halftone grids do not align exactly with the display space grid. It is a complex process to consistently align each halftone cell with the display space grid because the grid size of the halftone cell is normally not the same grid size as the display space and the matrix of halftone cells is typically at a different angle of orientation from the display space grid. If a threshold value is generated for each pixel of the display space, an infinite amount of different halftone cells would have to be computed to address each possible configuration of pixel locations within a cell.
The problem of aligning the halftone cell to the display space is illustrated by FIG. 1. The halftone cells are mapped at an angle to the matrix of pixels of the display space. Although one vertex of the cell 50 maps directly to a pixel location (in FIG. 1 pixel locations occur at the intersection of the grid lines), the remaining vertices 30, 40, 60 do not. Similarly, the adjoining halftone cell, having vertices 10, 20, 30, 40, does not align precisely with the pixel matrix. Because the relative pixel locations within each halftone cell vary from halftone cell to halftone cell, the threshold values generated for each pixel location would be different in each halftone cell.
To overcome this problem, a technique has been devised to align the halftone cells with the pixel matrix with the minimal of error wherein the vertices of the halftone cell are rounded off to the closest pixel. This may be visualized by referring to FIG. 2a. Utilizing the length of one side of a cell R.sub.d which directly corresponds to the user specified halftone frequency and the desired halftone cell angle with respect to the coordinate space .theta..sub.d, the revised cell frequency value is determined according to the following equations: EQU a=INT[R.sub.d cos(.theta..sub.d)] EQU b=INT[R.sub.d sin(.theta..sub.d)]
where R.sub.d is the desired length of a side of the halftone cell, .theta..sub.d represents the desired angle of the halftone cell with respect to the display space, INT represents an integer rounding function which rounds the vertex to the closest pixel. The "a" value represents the incremental integer amount (in units such as pixels) from one vertex to the adjacent vertex along a first axis (e.g., the x axis) and "b" represents the incremental integer amount along the second axis (e.g., the y axis). Thus, the actual length of the halftone cell (R.sub.a) is equal to SQRT (a.sup.2 +b.sup.2) and the actual angle is .theta..sub.a, where .theta..sub.a is equal to ARCTAN (b/a) and SQRT represents a square root function and ARCTAN represents an arctangent function. Hereinafter .theta.d is referred to as the "desired halftone angle" and .theta..sub.a is referred to as the "actual halftone angle". R.sub.d is referred to as the "desired cell frequency", and R.sub.a is the "actual cell frequency." Using the actual halftone angle .theta..sub.a, the actual cell frequency R.sub.a, and the values a and b, the adjusted halftone cells can be constructed. The adjusted halftone cells can be constructed, as illustrated in FIG. 2b, across the display space to complete the mapping of halftone cells to the matrix of display space. The actual halftone cells constructed are of equal size and align with the pixels of the display space whereby one single threshold matrix is applicable to all halftone cells.
The drawback to this technique is the error introduced by adjusting the halftone cell. The angle of the actual halftone cell to the display coordinate space (.theta..sub.a) and the length of a side of the actual halftone cell (R.sub.a) vary slightly from the desired angle and frequency (.theta..sub.d and R.sub.d) introducing a small error.
The error between the actual frequency R.sub.a, the actual angle .theta..sub.a and the desired frequency R.sub.d and the desired angle .theta..sub.d can be decreased by constructing "supercells," as illustrated in FIG. 3, which are composed of a plurality of halftone cells. The angle of the supercell to the display space and the actual frequency of the halftone cell can be adjusted to be quite close to the user desired angle and frequency by increasing the number of halftone cells contained in each supercell. The larger the supercell, the smaller the adjustment error, but the greater the size of memory required to store the supercell containing the threshold values. Thus, there is a tradeoff between precision, i.e. the size of the adjustment error, and the amount of memory required. Typically, the tradeoff is resolved by the user setting a predetermined tolerance and generating a supercell that is within the tolerance. For example, if the user specified angle is 15.degree. and the tolerance is set to be 0.01.degree., a supercell would be generated that has an angle within the range of 14.99.degree. to 15.01.degree.. Once the size of the halftone cell is determined, the cells are "stitched" together across the display space.
The amount of memory required to share the threshold array is very important with respect to the cost and performance of the system. Depending upon the tolerance of angle and frequency specified by a user, the storage of information can take up a lot of memory. In addition, typical storage techniques fluctuate according to the angle of the halftone cell relative to the display space.